class Solution {
public:
    bool search(vector<vector<char>>& board, string& word, 
                vector<vector<int>>&mem, int row, int col, int index){
        
        if(index == word.size()) return true;
        if(row < 0 || row >= board.size() || col < 0 || col >= board[0].size())
            return false;

        if(word[index] == board[row][col] && mem[row][col]==0){
            mem[row][col] = 1;
            bool flag = search(board, word, mem, row-1, col, index+1) || \
                        search(board, word, mem, row+1, col, index+1) || \
                        search(board, word, mem, row, col-1, index+1) || \
                        search(board, word, mem, row, col+1, index+1);
            mem[row][col] = 0;
            return flag;
        }
        return false;
    }

    bool exist(vector<vector<char>>& board, string word) {
        
        int m = board.size(), n = board[0].size();
        if(m*n < word.size()) return false;
        
        vector<vector<int>> mem(m, vector<int>(n, 0));

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(search(board, word, mem, i, j, 0)) 
                    return true;
            }
        }

        return false;
    }
};